package com.zk.algorithm;

import com.zk.algorithm.annotation.Finished;
import com.zk.algorithm.annotation.JianZhiOffer;

/**
 * 19. 正则表达式匹配
 */
@JianZhiOffer
@Finished(false)
public class RegexMatch {

    public boolean match(String str, String pattern) {
        if (str == null || pattern == null) {
            return false;
        }

        return match0(str, 0, pattern, 0);
    }

    private boolean match0(String str, int strIndex, String pattern, int patternIndex) {
        if (strIndex == str.length() && patternIndex == pattern.length()) {
            return true;
        }

        if (strIndex < str.length() && patternIndex == pattern.length()) {
            return false;
        }

        // 下一个字符是 * 号
        if (patternIndex + 1 < pattern.length() && pattern.charAt(patternIndex + 1) == '*') {

            if (str.charAt(strIndex) == pattern.charAt(patternIndex) ||
                    (pattern.charAt(patternIndex) == '.' && strIndex < str.length())) {
                return
                        // * 匹配 1 个字符
                        // str: a b c d
                        //        ↑↑
                        //      str 箭头往后移动 1 位
                        //
                        //   p: a b * c d
                        //        ↑  ↑
                        //   pattern 箭头向后移动 2 位
                        match0(str, strIndex + 1, pattern, patternIndex + 2) ||
                        // 模式不变
                        // str: a b b c d
                        //        ↑↑
                        //      str 箭头往后移动 1 位
                        //
                        //   p: a b * c d
                        //        ↑
                        match0(str, strIndex + 1, pattern, patternIndex) ||
                        // * 匹配 0 个字符
                        //
                        // str: a c d
                        //        ↑
                        //   p: a b * c d
                        //        ↑  ↑
                        //   pattern 箭头往后移动两位
                        // 即 忽略 b*，从 后续 的 cd 开始匹配
                        match0(str, strIndex, pattern, patternIndex + 2);
            } else {
                match0(str, strIndex, pattern, patternIndex + 2);
            }

        }

        // a. 匹配 ab
        // ab 匹配 ab
        // 继续匹配下一个字符即可
        if (str.charAt(strIndex) == pattern.charAt(patternIndex) ||
                (pattern.charAt(patternIndex) == '.' && strIndex < str.length())) {
            return match0(str, strIndex + 1, pattern, patternIndex + 1);
        }

        return false;
    }

    public static void main(String...args) {
        Utils.println(new RegexMatch().match("aaa", "a.a"));
        Utils.println(new RegexMatch().match("aa", "ab*ac*"));
        Utils.println(new RegexMatch().match("aaa", "ab*a"));
    }

}
